Not Applicable.
The present invention relates generally to data processing and, more particularly, to systems for displaying maps.
As is known in the art, advances in satellite imaging techniques have provided the ability to acquire highly detailed geographical map models. Such models enable interactive visual exploration of massive data sets, much of which is spatial in nature, generated with respect to an underlying geographic domain. For example, geographic information systems deal with the problem of capture, storage and display of large amounts of data with spatial information, such as weather and elevation information. Large telecommunications networks are visualized over an underlying global map. Thus, one of the major challenges facing any interactive system for visualizing such data is the problem of rendering the underlying spatial domain, which could be a political or topographical map of a region, or even a three-dimensional terrain. Such map data can be extremely complex in its finest detail. For example the so-called Tiger data provided by the U.S. Census Bureau contains U.S. maps with a few hundred million vertices occupying over 30 GB of storage.
The maps created by known techniques are seldom optimized for rendering efficiency and can usually be replaced with far fewer primitives, e.g., vertices and chains, without any loss in visual fidelity. In order to further improve the rendering speed and quality, known systems typically compute several versions of these maps. More detailed versions can be used when the object is very close to the viewer, and are replaced with coarser representations as the object recedes. The level of refinement can be adapted in different areas depending on the viewing parameters, which is commonly referred to as view-dependent simplification strategy. In addition, conventional systems can utilize simplification algorithms that are static or dynamic depending upon whether the refinement is performed as a preprocessing step or as part of the rendering loop.
It would, therefore, be desirable to provide a map simplification system that overcomes the aforesaid and other disadvantages.
The present invention provides a map simplification system for interactively maintaining a planar subdivision, e.g., arrangement of polylines, at varying levels of detail that preserves the shape features of the region, e.g., the essential geometric and topological characteristics. The system provides scalability, real-time performance, and robustness in comparison to conventional geometric map simplification systems. While the invention is primarily shown and described in conjunction with map simplification, it is understood that the invention is applicable to systems in general in which relatively large amounts of data are displayed.
In one aspect of the invention, a system simplifies a map by generating voronoi diagrams for a plurality of non-intersecting chains that define the map and removing non-compliant shortcut segments based upon the voronoi diagrams. The system removes non-proximate shortcut segments based upon the voronoi diagrams. In one embodiment, the system determines shortest paths from the compliant, proximate segments to provide a simplified map.